#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_WORD_SIZE 50

typedef struct TSTnode {
    char data[MAX_WORD_SIZE];
    struct TSTnode *left;
    struct TSTnode *middle;
    struct TSTnode *right;
} TSTNode;

TSTNode *createTSTNode(char *data) {
    TSTNode *newNode = (TSTNode*) malloc(sizeof(TSTNode));
    strcpy(newNode->data, data);
    newNode->left = NULL;
    newNode->middle = NULL;
    newNode->right = NULL;
    return newNode;
}

TSTNode *insertTST(TSTNode *root, char *data) {
    if (!root) {
        root = createTSTNode(data);
    } else if (strcmp(data, root->data) < 0) {
        root->left = insertTST(root->left, data);
    } else if (strcmp(data, root->data) > 0) {
        root->right = insertTST(root->right, data);
    } else {
        root->middle = insertTST(root->middle, data);
    }
    return root;
}

TSTNode *searchTST(TSTNode *root, char *data) {
    if (!root) {
        return NULL;
    } else if (strcmp(data, root->data) < 0) {
        return searchTST(root->left, data);
    } else if (strcmp(data, root->data) > 0) {
        return searchTST(root->right, data);
    } else {
        return root;
    }
}

size_t calculateTSTSize(TSTNode* root) {
    if (!root) {
        return 0;
    }
    size_t size = sizeof(TSTNode);
    size += calculateTSTSize(root->left);
    size += calculateTSTSize(root->middle);
    size += calculateTSTSize(root->right);
    return size;
}



typedef struct binaryNode {
    char data[MAX_WORD_SIZE];
    // char *data;
    struct binaryNode *left;
    struct binaryNode *right;
} BinaryNode;

BinaryNode *createBinaryNode(char *data) {
    BinaryNode *newNode = (BinaryNode*) malloc(sizeof(BinaryNode));
    strcpy(newNode->data, data);
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

BinaryNode *insertBinary(BinaryNode *root, char *data) {
    if (!root) {
        root = createBinaryNode(data);
    } else if (strcmp(data, root->data) < 0) {
        root->left = insertBinary(root->left, data);
    } else {
        root->right = insertBinary(root->right, data);
    }
    return root;
}

BinaryNode *searchBinary(BinaryNode *root, char *data) {
    if (!root) {
        return NULL;
    } else if (strcmp(data, root->data) < 0) {
        return searchBinary(root->left, data);
    } else if (strcmp(data, root->data) > 0) {
        return searchBinary(root->right, data);
    } else {
        return root;
    }
}

size_t calculateBinarySize(BinaryNode* root) {
    if (!root) {
        return 0;
    }
    size_t size = sizeof(BinaryNode);
    size += calculateBinarySize(root->left);
    size += calculateBinarySize(root->right);
    return size;
}

typedef struct trieNode {
    char data;
    int isEndOfWord;
    struct trieNode *children[26];
} TrieNode;

TrieNode *createTrieNode(char data) {
    TrieNode *newNode = (TrieNode*) malloc(sizeof(TrieNode));
    newNode->data = data;
    newNode->isEndOfWord = 0;
    for (int i = 0; i < 26; i++) {
        newNode->children[i] = NULL;
    }
    return newNode;
}

TrieNode *insertTrie(TrieNode *root, char *data) {
    if (!root) {
        root = createTrieNode(*data);
    }
    if (*data < root->data) {
        root->children[*data - 'a'] = insertTrie(root->children[*data - 'a'], data);
    } else if (*data > root->data) {
        root->children[*data - 'a'] = insertTrie(root->children[*data - 'a'], data);
    } else {
        if (*(data + 1)) {
            root->children[*data - 'a'] = insertTrie(root->children[*data - 'a'], data + 1);
        } else {
            root->isEndOfWord = 1;
        }
    }
    return root;
}

TrieNode *searchTrie(TrieNode *root, char *data) {
    if (!root) {
        return NULL;
    }
    if (*data < root->data) {
        return searchTrie(root->children[*data - 'a'], data);
    } else if (*data > root->data) {
        return searchTrie(root->children[*data - 'a'], data);
    } else {
        if (*(data + 1)) {
            return searchTrie(root->children[*data - 'a'], data + 1);
        } else {
            if (root->isEndOfWord) {
                return root;
            } else {
                return NULL;
            }
        }
    }
}

size_t calculateTrieSize(TrieNode* root) {
    if (!root) {
        return 0;
    }
    size_t size = sizeof(TrieNode);
    for (int i = 0; i < 26; i++) {
        size += calculateTrieSize(root->children[i]);
    }
    return size;
}

int main() {
    TSTNode *tstRoot = NULL;
    BinaryNode *binaryRoot = NULL;
    TrieNode *trieRoot = NULL;

    clock_t start, end;
    double cpu_time_used;

    FILE *file = fopen("strings1.txt", "r");
    char line[1024];
    double timestamp1=0,timestamp2=0,timestamp3=0;
    while (fgets(line, 1024, file)) {
        char *token;
        token = strtok(line, ",");
        double st1,st2,st3,st4;
        while (token != NULL) {
            // printf("%s\n", token);
            st1 = clock();
            tstRoot = insertTST(tstRoot, token);
            st2 = clock();
            timestamp1 += ((double)(st2-st1)) / CLOCKS_PER_SEC;
            binaryRoot = insertBinary(binaryRoot, token);
            st3 = clock();
            timestamp2 += ((double)(st3-st2)) / CLOCKS_PER_SEC;
            trieRoot = insertTrie(trieRoot, token);
            st4 = clock();
            timestamp3 += ((double)(st4-st3)) / CLOCKS_PER_SEC;
            token = strtok(NULL, ",");
        }
    }
    fclose(file);
    // compress(tstRoot);
    size_t tstSize = calculateTSTSize(tstRoot);
    printf("TST size: %zu bytes\n", tstSize);
    // printf("TST space used: %d\n", sizeof(TSTNode));
    size_t binarySize = calculateBinarySize(binaryRoot);
    printf("Binary tree size: %zu bytes\n", binarySize);

    size_t trieSize = calculateTrieSize(trieRoot);
    printf("Trie size: %zu bytes\n", trieSize);
    // printf("Binary space used: %d\n", sizeof(BinaryNode));
    // printf("Trie space used: %d\n", sizeof(TrieNode));
    printf("done\n");
    // // the sapce is smaller than trie and a little bit large than bianry
    start = clock();
    TSTNode *result_tst = searchTST(tstRoot, "ipbmtjybtou");
    if (result_tst) {
        printf("it exists in the TST\n");
    }
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC ;
    printf("TST insert and search time: %f\n", timestamp1+cpu_time_used);

    start = clock();
    BinaryNode *result_binary = searchBinary(binaryRoot, "ipbmtjybtou");
    if (result_binary) {
        printf("it exists in the Binary_Tree\n");
    }
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Binary insert and search time: %f\n", timestamp2+cpu_time_used);

    start = clock();
    TrieNode *result_trie1 = searchTrie(trieRoot,"ipbmtjybtou");
    // TrieNode *result_trie2 = searchTrie(trieRoot,"vhsmhvohyinh");
    // TrieNode *result_trie3 = searchTrie(trieRoot,"kelfmiybcj");
    if (result_trie1) {
        printf("it exists in the Trie\n");
    }
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Trie insert and search time: %f\n", timestamp3+cpu_time_used);
      
    return 0;
}






